package com.clstu.sort;

import java.util.Arrays;

/**
 * 演示选择排序过程,以及优化(如果不用交换,就不交换)
 *
 */
public class SelectSort {
    public static void main(String[] args) {
        //测试选择排序
//        int[] arr= {6,5,4,3,2,1};
//        selectSort(arr);
        //测试一下选择排序的速度
        //创建一个80000容量的随机数组
        int[] arr = new int[80000];
        //初始化
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random()*80000);
        }
        long start = System.currentTimeMillis();
        selectSort(arr);
        long end = System.currentTimeMillis();
        System.out.println("选择法排序80000条数据耗时:"+(end-start)+"ms");//1887ms
        //测试一下情况好的情况下
        long start1 = System.currentTimeMillis();
        selectSort(arr);
        long end1 = System.currentTimeMillis();
        System.out.println("选择法排序80000(有序的)条数据耗时:"+(end1-start1)+"ms");//744ms,(优化有效果)
        //可以得出,速度明显快于冒泡法排序,时间复杂度同为O(n*n),快的精髓在于 减少了交换语句的执行次数.
        //但是在数组比较有序的情况下,冒泡排序的优化起的作用更大.选择法的遍历次数仍然不变
    }

    //编写方法实现选择排序
    public static void selectSort(int[] arr){
        //思路分析:
        //选择排序过程:
        //    依次扫描,先假定第一个数就是最小数和最小下标
        //    扫描记录过程中最小数的下标和数值,扫描结束,最小下标的数据就跟扫描的第一个数交换,最小数确定了
        //    再从第二个数开始扫描...最终就有序了
        // 优化:如果最小数的下标就是扫描的第一个,则不用交换
        int min ;
        int minIndex;
        for (int i = 0; i < arr.length - 1; i++) {
            //假定扫描的第一个数就是最小数
            min = arr[i];
            minIndex = i;
            //找到每一轮的最小数以及下标
            for (int j = i; j < arr.length; j++) {
                if(min>arr[j]){
                    min = arr[j];
                    minIndex = j;
                }
            }
            //交换,确定第i个最小数
            if(minIndex!=i){
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
            //打印每一次的排序结果
//            System.out.println("第"+(i+1)+"次排序后:"+ Arrays.toString(arr));
        }
    }
}
